package baoliDigui;

//N皇后问题:在N*N的棋盘上摆放N个皇后 要求任意两个皇后不得在同一行，同一列，同一条斜线
//N=1 return 1
//N=2  ||  3   return0
//N=8  返回92
/*
* 思路：按行摆  记录已经摆好的皇后的位置  下一步摆的时候只用考虑是否同列同斜线即可
* */
public class N_Queen {

    public static int num1(int n){
        if (n<1){
            return 0;
        }
        int[] record = new int[n];
        return process1(0,record,n);
    }

    /*
    * 当前来到第i行  record数组表示之前已经摆放好的  数组下标表示行  值为位置
    * n代表一共有多少行  为固定参数
    * 返回值是，摆放所有的皇后一共有多少种合理的摆法
    * */
    public static int process1(int i,int[] record,int n){
        if (i==n){     //终止行
            return 1;
        }
        int res=0;
        for (int j=0;j<n;j++){
            //把当前i行的皇后 放在j列 判断和之前已经放好的是否有冲突 如果没有 则放在该位置  如果有冲突 则认为无效
            if (isValid(record,i,j)){
            record[i] = j;
            res +=process1(i+1,record,n);
            }
        }
        return res;
    }


    //返回： 第i行皇后  放在了j列 是否有效
    public static boolean isValid(int[] record,int i,int j){
        for (int k=0;k<i;k++){
            //判断是否在同一个斜线 利用了等腰三角形的原理 两个直角边的绝对值相等则为在同一个斜线
            if (j==record[k]  || Math.abs(record[k] - j) == Math.abs(i-k)){
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {

    }
}
